package shujvjiegou.week8;

import java.util.*;

/**
 * @Author JetZhang
 * @Date 2021/10/31
 */
public class T2 {

    private Queue<T_Node> queue;

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        String[] arr = scanner.nextLine().split(" ");
        T_Node t_node = new T_Node(arr[0]);
        for (int i = 1; i < arr.length; i++) {
            new T2().insert(t_node, arr[i]);
        }
        System.out.println(new T2().MinDepth(t_node));
    }

    private int MinDepth(T_Node root) {
        if (root == null) return 0;
        Queue<T_Node> queue = new LinkedList<>();
        if (!root.data.equals("None")) {
            queue.add(root);
        }
        int level = 0;
        int l = 0;
        int r = 0;
        while (!queue.isEmpty()) {
            level++;
            int size = queue.size();
            for (int i = 0; i < size; i++) {
                T_Node t_node = queue.poll();
                if (t_node.lChild == null && t_node.rChild == null) {
                    if (t_node.data.equals("None")) {
                        level--;
                    }
                    if (l == 0 || r == 0) {
                        level = l + r + 1;
                    }
                    return level;
                }
                if (t_node.lChild != null && !t_node.lChild.data.equals("None")) {
                    l++;
                    queue.add(t_node.lChild);
                } else {
                    if (l != 0) {
                        return level;
                    }
                }
                if (t_node.rChild != null && !t_node.rChild.data.equals("None")) {
                    r++;
                    queue.add(t_node.rChild);
                } else {
                    if (r != 0) {
                        return level;
                    }
                }
            }
        }
        return level;
    }

    private void insert(T_Node t_node, String s) {
        queue = new LinkedList<>();
        queue.add(t_node);
        while (!queue.isEmpty()) {
            t_node = queue.poll();
            if (!t_node.data.equals("None")) {
                if (t_node.lChild == null) {
                    t_node.lChild = new T_Node(s);
                    break;
                } else
                    queue.add(t_node.lChild);

                if (t_node.rChild == null) {
                    t_node.rChild = new T_Node(s);
                    break;
                } else {
                    queue.add(t_node.rChild);
                }
            }
        }
    }

}

class T_Node {
    T_Node lChild;
    T_Node rChild;
    String data;

    public T_Node(String data) {
        lChild = null;
        rChild = null;
        this.data = data;
    }
}
